#include<iostream>
using namespace std;

/*
编写一个算法来判断一个数n是不是快乐数。
"快乐数"定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，
然后重复这个过程直到这个数变为1，也可能是无限循环但始终变不到1。如果可以变为1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：
输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
*/

int getSum(int num){
    int result=0;
    while(num>0){
        result+=(num%10)*(num%10);
        num/=10;
    }
    return result;
}

bool isPrime(int v){
    for(int i=2;i<v/2+1;i++){
        if(v%i==0)return false;
    }
    return true;
}

class node{
public:
    int val;
    node*next;
    node(){
        val=0;
        next=0;
    }
    node(int v){
        val=v;
        next=0;
    }
};

class hashTable{
public:
    node**array;
    int P;//当P取小于哈希表长的最大质数时，产生的哈希函数较好
    int len;
    hashTable(int len);
    bool append(int v);
    ~hashTable();
};

hashTable::hashTable(int len){
    this->len=len;
    array=new node*[len];//节点指针数组
    for(int i=0;i<len;i++)
        array[i]=new node(-1);
    for(int i=len-1;i>0;i--){
        if(isPrime(i)){
            P=i;
            break;
        }
    }
}

bool hashTable::append(int v){
    //数值v已经存在返回false,否则返回true
    int position=v%P;
    node*ptr=array[position];
    while(ptr->next!=0){
        ptr=ptr->next;
        if(ptr->val==v){
            return false;
        }
    }
    ptr->next=new node(v);
    return true;
}

hashTable::~hashTable(){
    for(int i=0;i<this->len;i++){
        node*ptr=array[i]->next;
        while(ptr!=0){
            node*temp=ptr;
            ptr=ptr->next;
            delete temp;
        }
    }
    delete[]this->array;
}

bool isHappy(hashTable h,int num){
    bool result=false;
    h.append(num);
    while(true){
        num=getSum(num);
        cout<<num<<endl;
        if(num==1){
            result=true;
            break;
        }
        if(h.append(num)==false){
            result=false;
            break;
        }
    }
    return result;
}

int main(){
    hashTable h(6);
    cout<<isHappy(h,19);
    
    return 0;
}